package hwOne3;

import edu.princeton.cs.algs4.StdOut;

// 1.3.19 1.3.20
public class LinkedList<Item>  {
    private Node first; // 链表首结点

    private class Node {
        int item; // 结点存储的数据
        Node next; // 指向下一个结点
    }

    // 删除链表的尾结点
    public void deleteLast() {
        if (first == null) {
            // 如果链表为空，直接返回
            return;
        }

        if (first.next == null) {
            // 如果链表只有一个结点，删除该结点
            first = null;
            return;
        }

        Node current = first;
        // 遍历链表直到找到倒数第二个结点
        while (current.next.next != null) {
            current = current.next;
        }

        // 将倒数第二个结点的next设置为null，删除尾结点
        current.next = null;
    }

    public void delete(int k) {
        if (k == 0) {
            return;
        }
        int count = 0;
        Node current = first;
        while (count >= k || current != null) {
            // 遍历到 k 前一个元素，并且第 k 个元素不为空
            StdOut.println("cur:" + current.item);
            if (count == k - 1 && current.next != null) {
                // 跳过下一个元素
                current.next = current.next.next;
                break;
            }
            current = current.next;
            count++;
        }
    }

    // 辅助方法：添加结点到链表末尾
    public void add(int item) {
        if (first == null) {
            first = new Node();
            first.item = item;
            return;
        }

        Node current = first;
        while (current.next != null) {
            current = current.next;
        }

        Node newNode = new Node();
        newNode.item = item;
        current.next = newNode;
    }

    // 辅助方法：打印链表
    public void printList() {
        Node current = first;
        while (current != null) {
            System.out.print(current.item + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.print("原链表: ");
        list.printList();

        list.delete(2); // 删除尾结点
        System.out.print("删除k个节点: ");
        list.printList();
    }
}